﻿/**
 *	哈希映射表的基类，实现基本算法，参考live555中的代码
 *@author  吴建凰
 *@date		2015年3月27日
 */

#ifndef HASH_TABLE_H
#define HASH_TABLE_H
#include "ossType.h"
#include <ossObject.h>

/**
 *		哈希表节点，该节点同时充当key和value的角色
 */
class OssHashKey : public OssObject
{
public:
	OssHashKey();
	virtual ~OssHashKey();

	/**
	 *		生成hash值
	 */
	virtual DWord HashVal() = 0;

	/**
	 *		比较键值是否一样
	 */
	virtual Bool CompareKey(OssHashKey* obj) = 0;

public:
	OssHashKey* m_fNext;
};

class OssHashTable : public OssObject
{
public:
	OssHashTable(Bool bFreeEntry = true);
	virtual ~OssHashTable();

	/**
	 *		增加一个节点
	 *@return	如果存在同样的节点则保留原来的节点，并返回原来的节点
	 *			新增成功返回NULL
	 */
	virtual OssHashKey* Add(OssHashKey* entry);

	/**
	 *		删除一个节点
	 *@key		入口只作为key用
	 *@return	找到并移除返回原来的entry,否则返回NULL
	 *@note		不释放entry的空间
	 */
	virtual OssHashKey* Remove(OssHashKey* key);

	/**
	 *		根据key查找入口
	 *@key		入口只作为key用
	 *@return	找到则返回对应key的entry
	 *			否则返回NULL
	 */
	virtual OssHashKey* Lookup(OssHashKey* key) const;
  
	//元素个数
	virtual DWord numEntries() const;

    /**
	 *		清除所有的节点,所有节点会根据bDel变量执行delete操作
	 *@bDel		是否执行delete动作，默认执行
	 */
	virtual void Clear(Bool bDel = TRUE); 

    /**
     *      获取得到第一个hash元素
     */
    OssHashKey* FirstItem();

    /**
     *      当前元素获取下一个节点
     */
    OssHashKey* NextItem(OssHashKey* pCurrentPos);
private:

	/**
	 *		通过key找入口
	 *@key		充当key的entry
	 *@index	返回对应key的index值
	 *@return	找到返回原来的entry
	 *			没找到返回NULL
	 */
	OssHashKey* lookupKey(OssHashKey* key, DWord& index) const;

    /**
	 *		插入一个新入口 
	 */
	void insertNewEntry(DWord index, OssHashKey* entry);

    // used to implement "insertNewEntry()"
	
	void deleteEntry(DWord index, OssHashKey* entry);
    // used to implement "deleteEntry()"

	void rebuild(); // rebuilds the table as its size increases

	/**
	 *		生成哈希索引
	 */
	DWord hashIndexFromKey(OssHashKey* key) const;
private:
  OssHashKey**	m_fBuckets; // pointer to bucket array
  DWord             m_fNumBuckets;
  DWord             m_fNumEntries;
  DWord             m_fRebuildSize;
  DWord             m_fMask;
  Bool			    m_freeEntry;//析构时是否释放entry
};

/**
 *      遍历hashmap
 *@pos      接收当前遍历的对象，类型为 type*
 *@hmap     当前遍历的hashmap，需要取地址
 *@type     声明当前的数据类型
 *@notes    本方法不是安全的方法，不能将当前遍历的对象删除，否则会出异常
 */
#define  ITEARATE_HASH_ENTRY(pos,hmap,type ) \
    for (pos = (type*)(hmap)->FirstItem();pos != NULL ;pos = (type*)(hmap)->NextItem(pos))

/**
 *      遍历hashmap
 *@pos      接收当前遍历的对象，类型为 type*
 *@hmap     当前遍历的hashmap，需要取地址
 *@type     声明当前的数据类型
 *@notes    本方法是安全的方法，能将当前遍历的对象删除
 */
#define  ITEARATE_HASH_ENTRY_SAFE(pos,n,hmap,type ) \
    for (pos = (type*)(hmap)->FirstItem(),(pos ? (n = (type*)(hmap)->NextItem(pos)) : NULL);pos != NULL ; \
                pos = n,(pos ? (n = (type*)(hmap)->NextItem(pos)) : NULL))


 /*
 * MEMBER在结构体中的相对位置
*/
#ifndef OssOffsetof
#define OssOffsetof(TYPE, MEMBER) ((unsigned long) &(((TYPE *)0)->MEMBER))
#endif

#define OssHashEntry(ptr, type, member) ((type *)(((char*)(ptr)) - OssOffsetof(type, member)))

/**
 *		安全遍历hash，在遍历时可以执行删除操作
 */
#define OssHashForEachEntrySafe(pos,n,hmap,member,type) \
		for (pos = ((hmap)->FirstItem() ? OssHashEntry((hmap)->FirstItem(), type, member) : NULL), \
		n=((pos && (hmap)->NextItem(&(pos->member))) ? (OssHashEntry((hmap)->NextItem(&pos->member), type, member)) : NULL); \
		pos != NULL; \
		pos = n, n = ((pos && (hmap)->NextItem(&pos->member))) ? (OssHashEntry((hmap)->NextItem(&pos->member), type, member)) : NULL)

/**
 *		非安全遍历，在遍历时不能执行删除操作
 */
#define OssHashForEachEntry(pos,hmap,member,type) \
	for (pos = ((hmap)->FirstItem() ? OssHashEntry((hmap)->FirstItem(), type, member) : NULL); \
		pos != NULL; \
		pos = ((hmap)->NextItem(&pos->member)) ? (OssHashEntry((hmap)->NextItem(&pos->member), type, member)) : NULL)


#endif
